googologywikiaorg-20200223-history
User blog:Kyodaisuu/A program of Kirby-Paris hydra
A program which calculates \(f_{\epsilon_0+1}(10)\) was posted at googology thread of Japanese BBS 2ch.net (anonymous author; now GWiki accout was created.).BASIC program of \(\epsilon_0\) level Aycabta translated this program to C and Ruby.Translation of the program to C and Ruby This program is a simple implementation of Kirby-Paris hydra. Bashicu now calls this algorithm primitive sequence system. BashicuHyudora also made an extended version of this program "Pair sequence system". dim A(Infinity):B=9 for C=0 to 9 for D=0 to B A(D)=D next for E=B to 0 step -1 B=B*B for F=0 to E if A(E-F) Linear array and ordinal In this program, linear array A is stored in parameters A(0) to A(E). For example, when E=3, A(0)=0, A(1)=1, A(2)=2 and A(3)=3, we express this linear array as (0,1,2,3). The linear array is related to an ordinal. Ordinal \(\alpha < \epsilon_0\) is expressed with linear array as follows. # Draw Kirby-Paris hydra of the ordinal \(\alpha\). For example, the figure represents \(\omega^{\omega^\omega+\omega^3}+\omega^{\omega^2+1}\), as explained in Kirby and Paris (1982).Kirby, L.; Paris, J. (1982), "Accessible independence results for Peano arithmetic" # Start from root node. # Going up one node from root node is expressed as adding an entry with the value 0. # Going up one node is expressed as adding an entry with "(value of the previous entry) + 1". # Going down \(n\) nodes and going up one node for adjacent segment is expressed as adding an entry with "(value of the previous entry) - n + 1". # Thus, the value of each entry expresses the height of the node from the root node - 1. # In the figure, first going up the highest \(\omega^{\omega^\omega}\) segment is expressed as (0,1,2,3). Then going down 3 nodes and going to the adjcent segment, entries (1,2,2,2) is added. After that, the segment (0,1,2,2,1) is added. Thus, the hydra tree is expressed as a sequence of (0,1,2,3,1,2,2,2,0,1,2,2,1). # We express this correspondence with the equation \(\omega^{\omega^\omega+\omega^3}+\omega^{\omega^2+1} = (0,1,2,3,1,2,2,2,0,1,2,2,1)\). Here are examples. \begin{eqnarray*} 1 &=& (0) \\ 2 &=& (0,0) \\ 3 &=& (0,0,0) \\ \omega &=& (0,1) \\ \omega+2 &=& (0,1,0,0) \\ \omega \cdot 2 &=& (0,1,0,1) \\ \omega^2 &=& (0,1,1) \\ \omega^2+\omega &=& (0,1,1,0,1) \\ \omega^3 &=& (0,1,1,1) \\ \omega^\omega &=& (0,1,2) \\ \omega^{\omega^\omega} &=& (0,1,2,3) \\ \omega^{\omega^{\omega^\omega}} &=& (0,1,2,3,4) \\ \omega^{\omega^{(\omega^\omega+1)}} &=& (0,1,2,3,4,2) \\ \omega^{\omega^{\omega^{\omega^\omega}}} &=& (0,1,2,3,4,5) \\ \end{eqnarray*} Reading codes dim A(Infinity):B=9 A is for linear array and B is for the value. for C=0 to 9 This C loop repeats the \(B = f_{\epsilon_0}(B)\) calculation 10 times, therefore calculating \(f_{\epsilon_0+1}(10)\). for D=0 to B A(D)=D next It sets ordinal \(\omega\)^^\(B=(0,1,2,3,...,B)\). for E=B to 0 step -1 This loop is a little tricky because the value of E changes inside the loop. E represents the position of the last entry of the sequence, and therefore it starts from B. The remaining will be explained later. B=B*B At each step of cutting hydra head, B value is squared. If it is \(B=B+1\) and it is executed only for successor, it matches the Hardy hierarchyModified C code to calculate Hardy hierarchy and result.. As it uses \(B=B^2\), it is slightly stronger than Hardy hierarchy. for F=0 to E if A(E-F) It calculates G, the length of the sequence where the hydra tree is copied. For example, for (0,1,2,3), G=1, meaning that after (3) is cut, (2) is copied. For (0,1,2,3,0), G=0, meaning that the hydra head is not copied. For (0,1,2,3,1), G=4, meaning that after (1) is cut, (0,1,2,3) is copied. for H=1 to B*G A(E)=A(E-G):E=E+1 next When G=0, this loop is not calculated, meaning that the hydra head is not copied after cutting off. In this case, at the start of the next loop, E is decreased by one, meaning that the rightmost node was cut off. When G>0, this loop cuts one hydra head and makes B copies of hydra heads expressed with the length G sequence. A(E)=A(E-G) is the operation of copying. It starts from A(E), meaning that the rightmost head was cut off. After copying, E=E+1 is calculated, and therefore the E is 1 larger than the position of the rightmost sequence. At the start of the next loop, E is decreased by one (STEP -1), and therefore it is cancelled. next next End of loops. print B Output the result. At first, A(0) to A(9) are set as \(A(n)=n\). This sequence is expressed as (0,1,2,3,4,5,6,7,8,9), and parameter E is set as E=9, where E represents the position at the end of the sequence. Example calculation Example calculation for this simplified code was shown by the author of the program.Example calculation posted at 2ch.net dim A(Infinity):B=2 for D=0 to B A(D)=D next for E=B to 0 step -1 for F=0 to E if A(E-F) The array is first initialized to \((0,1,2) = \omega^{\omega}\). At the loop of F, G=1. At the loop of H, E=4 and the array becomes \((0,1,1,1) = \omega^3\). After that, it goes to the second loop of E and E is decreased to 3 by STEP -1. Therefore, it matches the rightmost position of the sequence (0,1,1,1). In this second loop of E, the array changes to \((0,1,1,0,1,1,0,1,1) = \omega^2 \cdot 3\). After this, the ordinal will decrease as *\((0,1,1,0,1,1,0,1,0,1,0,1) = \omega^2 \cdot 2 + \omega \cdot 3\) *\((0,1,1,0,1,1,0,1,0,1,0,0,0) = \omega^2 \cdot 2+\omega \cdot 2+3\) *\((0,1,1,0,1,1,0,1,0,1,0,0) = \omega^2 \cdot 2+\omega \cdot 2+2\) *\((0,1,1,0,1,1,0,1,0,1,0) = \omega^2 \cdot 2+\omega \cdot 2+1\) *\((0,1,1,0,1,1,0,1,0,1) = \omega^2 \cdot 2+\omega \cdot 2\) *From here, not showing all the process. *\((0,1,1,0,1,1,0,1) = \omega^2 \cdot 2+\omega\) *\((0,1,1,0,1,1) = \omega^2 \cdot 2\) *\((0,1,1,0,1,0,1,0,1) = \omega^2+\omega \cdot 3\) *\((0,1,1,0,1,0,1) = \omega^2+\omega \cdot 2\) *\((0,1,1,0,1) = \omega^2+\omega\) *\((0,1,1) = \omega^2\) *\((0,1,0,1,0,1) = \omega \cdot 3\) *\((0,1,0,1) = \omega \cdot 2\) *\((0,1) = \omega\) *\((0,0,0) = 3\) *\((0,0) = 2\) *\((0) = 1\) Sources Category:Blog posts Category:Blog posts about Bashicu matrix system